More and more, users are provided with the opportunity to store data at untrusted servers (e.g., third party, untrusted remote servers). For example, users may be able to access the remote storage via the internet in order to upload files for subsequent access or downloading (e.g., at a different location). As another example, some peer-to-peer (P2P) networks provide third party storage where the data is stored by a different agent or an entity other than the user (e.g., the user who uploaded or provided the data). As a non-limiting example, such an arrangement may be beneficial in order to provide other users with access to the data (e.g., based on considerations such as bandwidth usage and hosting capabilities).
In these settings, users may desire to check if their data has been tampered with or deleted by the storage server. In order to validate the data, the user may be required to download the data. If the outsourced data includes very large files or entire file systems, requiring the user to download the data will likely hinder validation and increase the expense (e.g., in terms of bandwidth and time), particularly if the client wishes to check the data frequently.
Consider online storage-outsourcing services (e.g., Amazon S3), outsourced database services [16], peer-to-peer storage [13, 19] and network file systems [12, 15]. The common concern in all these systems is the fact that the server (or peer) who stores the client's data is not necessarily trusted. Therefore, users would like to check if their data has been tampered with or deleted. However, outsourcing the storage of very large files (or whole file systems) to remote servers presents an additional constraint: the client should not download all stored data in order to validate it since this may be prohibitive in terms of bandwidth and time, especially if the client performs this check frequently (therefore authenticated data structures solutions [31] cannot be directly applied in this scenario).
Ateniese et al. [2] formalized this problem with a model called provable data possession (PDP). In this model, data (often represented as a file F) is preprocessed by the client, producing metadata that is used for verification purposes. The file is then sent to an untrusted server for storage, and the client may delete the local copy of the file. The client keeps some (possibly secret) information to check the server's responses later. The server proves the data has not been tampered with by responding to challenges sent by the client. The authors present several variations of their scheme under different cryptographic assumptions. These schemes provide probabilistic guarantees of possession, where the client checks a random subset of stored blocks with each challenge.
However, the PDP model and related schemes [2, 6, 11, 30] apply only to the case of static, archival storage, i.e., a file that is outsourced and never changes (one exception was developed simultaneously with this work [3] and is discussed in the related work section below). While the static model fits some application scenarios (e.g., libraries and scientific datasets), it is crucial to consider the dynamic case, where the client updates the outsourced data—by inserting, modifying, or deleting stored blocks or files—while maintaining data possession guarantees. Such a dynamic PDP (DPDP) scheme is essential in practical cloud computing systems for file storage [12, 15], database services [16], and peer-to-peer storage [13, 19].
As storage-outsourcing services and resource-sharing networks became popular, the problem of efficiently proving the integrity of data stored at untrusted servers has received increased attention. In the provable data possession (PDP) model, the client preprocesses the data and then sends it to an untrusted server for storage, while keeping a small amount of meta-data. The client later asks the server to prove that the stored data has not been tampered with or deleted (without downloading the actual data). However, the original PDP scheme applies only to static (or append-only) files.